package exercises.leetcode;

import exercises.newcoder.util.TreeNode;

import java.util.LinkedList;

/**
 * <a href="https://leetcode-cn.com/problems/er-cha-shu-de-jing-xiang-lcof/">
 * 剑指 Offer 27. 二叉树的镜像</a>
 *
 * <p><span color="#87CEEB">描述:</span>
 * 请完成一个函数，输入一个二叉树，该函数输出它的镜像。
 * <p>
 * 例如输入：
 * <pre>{@code
 *      4
 *    /   \
 *   2     7
 *  / \   / \
 * 1   3 6   9}</pre>
 * 镜像输出：
 *
 * <pre>{@code
 *      4
 *    /   \
 *   7     2
 *  / \   / \
 * 9   6 3   1
 * }</pre>
 *  
 * <p>
 * 示例 1：
 * <p>
 * 输入：root = [4,2,7,1,3,6,9]
 * 输出：[4,7,2,9,6,3,1]
 *  
 * <p>
 * 限制：
 * <p>
 * 0 <= 节点个数 <= 1000
 * <p>
 * 注意：本题与主站 226 题相同：https://leetcode-cn.com/problems/invert-binary-tree/
 *
 * @author or2
 * @date 2021年09月29日 时间: 23:01
 */
public class Offer27 {
    public TreeNode mirrorTree(TreeNode root) {
        if (root == null)
            return null;

        LinkedList<TreeNode> stack = new LinkedList<>();
        stack.push(root);

        while (!stack.isEmpty()) {
            TreeNode pop = stack.pop();
            TreeNode temp = pop.left;
            pop.left = pop.right;
            pop.right = temp;

            if (pop.left != null) stack.push(pop.left);
            if (pop.right != null) stack.push(pop.right);
        }

        return root;
    }

    public TreeNode mirrorTreeCustom(TreeNode root) {
        if (root == null)
            return null;

        Stack stack = new Stack();
        stack.push(root);

        while (!stack.isEmpty()) {
            TreeNode pop = stack.pop();
            TreeNode temp = pop.left;
            pop.left = pop.right;
            pop.right = temp;

            if (pop.left != null) stack.push(pop.left);
            if (pop.right != null) stack.push(pop.right);
        }

        return root;
    }

    private static class Stack {
        Node first;
        Node last;

        public boolean isEmpty() {
            return first == null;
        }

        public void push(TreeNode node) {
            if (first == null) {
                first = new Node();
                first.value = node;
                last = first;
            } else {
                last.next = new Node(node);
                Node p = this.last;
                last = last.next;
                last.pre = p;
            }
        }

        public TreeNode pop() {
            if (first == null) return null;

            TreeNode node;
            if (this.last == first) {
                node = this.last.value;
                this.last = null;
                first = null;
            } else {
                node = last.value;
                last = last.pre;
                last.next = null;
            }
            return node;
        }

        private static class Node {
            TreeNode value;
            Node pre;
            Node next;

            public Node() {
            }

            public Node(TreeNode value) {
                this.value = value;
            }
        }
    }
}
